Challenging the “Embarrassingly Sequential”: Parallelizing Finite State Machine-Based Computations through Principled Speculation

Finite-State Machine (FSM) applications are important for many domains. But FSM computation is inherently sequen-tial, making such applications notoriously difficult to par-allelize. Most prior methods address the problem through speculations on simple heuristics, offering limited applica-bility and inconsistent speedups. This paper provides some principled understanding of FSM parallelization, and offers the first disciplined way to exploit application-specific information to inform specula-tions for parallelization. Through a series of rigorous anal-ysis, it presents a probabilistic model that captures the rela-tions between speculative executions and the properties of the target FSM and its inputs. With the formulation, it pro-poses two model-based speculation schemes that automati-cally customize themselves with the suitable configurations to maximize the parallelization benefits. This rigorous treat-ment yields near-linear speedup on applications that state-of-the-art techniques can barely accelerate